/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class BusRoutes {
	public int numBusesToDestination(int[][] routes, int S, int T) {
		for (int i = 0; i < routes.length; i++) {
			Arrays.sort(routes[i]);
		}
		Set<Integer> visitedStation = new HashSet<>();
		visitedStation.add(S);
		Set<Integer> visitedRoutes = new HashSet<>();
		Queue<Integer> queue = new LinkedList<>();
		queue.add(S);
		int res = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int cur = queue.poll();
				if (cur == T) {
					return res;
				}
				for (int j = 0; j < routes.length; j++) {
					if (!visitedRoutes.contains(j) && Arrays.binarySearch(routes[j], cur) >= 0) {// 一条线路最多只加入一次
						visitedRoutes.add(j);
						for (Integer neib : routes[j]) {
							if (visitedStation.add(neib)) {// 如果之前没有访问过
								queue.offer(neib);
							}
						}
					}
				}
			}
			res++;
		}
		return -1;
	}

	private void addReach(int i, int j, Map<Integer, ArrayList<Integer>> reachable) {
		if (reachable.containsKey(i)) {
			reachable.get(i).add(j);
		} else {
			ArrayList<Integer> list = new ArrayList<>();
			list.add(j);
			reachable.put(i, list);
		}
	}

	public int numBusesToDestination2(int[][] routes, int S, int T) {
		Map<Integer, ArrayList<Integer>> reachable = new HashMap<>();// 同一条线路可达的
		System.out.println("start reachable");
		for (int[] is : routes) {
			for (int j = 0; j < is.length; j++) {
				for (int k = j + 1; k < is.length; k++) {
					addReach(is[j], is[k], reachable);
					addReach(is[k], is[j], reachable);
				}
			}
		}
		System.out.println("finish reachable");
		Set<Integer> visited = new HashSet<>();
		visited.add(S);
		Queue<Integer> queue = new LinkedList<>();
		queue.add(S);
		int res = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int cur = queue.poll();
				if (cur == T) {
					return res;
				}
				for (Integer neib : reachable.get(cur)) {
					if (visited.add(neib)) {// 如果之前没有访问过
						queue.offer(neib);
					}
				}
			}
			res++;
		}
		return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] routes = { { 1, 2, 7 }, { 3, 6, 7 } };
		int S = 1;
		int T = 6;
		System.out.println(new BusRoutes().numBusesToDestination(routes, S, T));
	}

}
